package org.hot100_1;

import org.leetcode.TreeNode;

public class leetcode47 {
    int count;
    public int pathSum(TreeNode root, int targetSum) {

        if (root==null){
            return 0;
        }
        //统计以root为根节点时，满足条件的路径是多少
        dfs(root,targetSum,0);
        //统计以root.left为根节点时，满足条件的路径是多少
        pathSum(root.left,targetSum);
        //统计以root.right为根节点时，满足条件的路径是多少
        pathSum(root.right,targetSum);

        return count;
    }

    private void dfs(TreeNode root,int targetSum,long sum){
        if (root==null){
            return;
        }
        sum = sum+root.val;
        if (sum==targetSum){
            count++;
        }

        dfs(root.left,targetSum,sum);
        dfs(root.right,targetSum,sum);
    }
}
